package linked;

import linked.base.ListNode;

public class Solution_23 {

    /**
     * 相邻的链表依次去做合并，结果存到后一个链表头结点
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        for (int i = 0; i < lists.length - 1; i++) {
            ListNode listNode = mergeList(lists[i], lists[i + 1]);
            lists[i + 1] = listNode;
        }
        return lists[lists.length - 1];
    }

    public ListNode mergeList(ListNode lNode, ListNode rNode) {
        ListNode firNode = new ListNode();
        ListNode curNode = firNode;
        while (lNode != null && rNode != null) {
            if (lNode.val < rNode.val) {
                curNode.next = lNode;
                lNode = lNode.next;
                curNode = curNode.next;
            } else {
                curNode.next = rNode;
                rNode = rNode.next;
                curNode = curNode.next;
            }
        }
        if (lNode != null) {
            curNode.next = lNode;
        } else {
            curNode.next = rNode;
        }
        return firNode.next;
    }

}
